{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Complexity of large contractions\n",
    "\n",
    "This notebook assesses computational complexity of `einsum` on large contractions. To generate data (pasted in the cells below), run:\n",
    "```sh\n",
    "GROWTH_SIZE=50 pytest -s tests/infer/test_enum.py -k growth\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot\n",
    "\n",
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'svg'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sizes = None\n",
    "costs = None\n",
    "times1 = None\n",
    "times2 = None\n",
    "\n",
    "\n",
    "def plot(title):\n",
    "    pyplot.figure(figsize=(8, 5)).patch.set_color(\"white\")\n",
    "    pyplot.title(\"{} data structures\".format(title))\n",
    "    for name, series in sorted(costs.items()):\n",
    "        pyplot.plot(sizes, series, label=name)\n",
    "    pyplot.xlabel(\"problem size\")\n",
    "    pyplot.xlim(0, max(sizes))\n",
    "    pyplot.legend(loc=\"best\")\n",
    "    pyplot.tight_layout()\n",
    "\n",
    "    pyplot.figure(figsize=(8, 5)).patch.set_color(\"white\")\n",
    "    pyplot.title(\"{} run time\".format(title))\n",
    "    pyplot.plot(sizes, times1, label=\"optim + compute\")\n",
    "    pyplot.plot(sizes, times2, label=\"compute\")\n",
    "    pyplot.xlim(0, max(sizes))\n",
    "    pyplot.xlabel(\"problem size\")\n",
    "    pyplot.ylabel(\"time (sec)\")\n",
    "    pyplot.legend(loc=\"best\")\n",
    "    pyplot.tight_layout()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sizes = [\n",
    "    3,\n",
    "    4,\n",
    "    5,\n",
    "    6,\n",
    "    7,\n",
    "    8,\n",
    "    9,\n",
    "    10,\n",
    "    11,\n",
    "    12,\n",
    "    13,\n",
    "    14,\n",
    "    15,\n",
    "    16,\n",
    "    17,\n",
    "    18,\n",
    "    19,\n",
    "    20,\n",
    "    21,\n",
    "    22,\n",
    "    23,\n",
    "    24,\n",
    "    25,\n",
    "    26,\n",
    "    27,\n",
    "    28,\n",
    "    29,\n",
    "    30,\n",
    "    31,\n",
    "    32,\n",
    "    33,\n",
    "    34,\n",
    "    35,\n",
    "    36,\n",
    "    37,\n",
    "    38,\n",
    "    39,\n",
    "    40,\n",
    "    41,\n",
    "    42,\n",
    "    43,\n",
    "    44,\n",
    "    45,\n",
    "    46,\n",
    "    47,\n",
    "    48,\n",
    "    49,\n",
    "    50,\n",
    "]\n",
    "costs = {\n",
    "    \"einsum\": [\n",
    "        1,\n",
    "        2,\n",
    "        3,\n",
    "        4,\n",
    "        5,\n",
    "        6,\n",
    "        7,\n",
    "        8,\n",
    "        9,\n",
    "        10,\n",
    "        11,\n",
    "        12,\n",
    "        13,\n",
    "        14,\n",
    "        15,\n",
    "        16,\n",
    "        17,\n",
    "        18,\n",
    "        19,\n",
    "        20,\n",
    "        21,\n",
    "        22,\n",
    "        23,\n",
    "        24,\n",
    "        25,\n",
    "        26,\n",
    "        27,\n",
    "        28,\n",
    "        29,\n",
    "        30,\n",
    "        31,\n",
    "        32,\n",
    "        33,\n",
    "        34,\n",
    "        35,\n",
    "        36,\n",
    "        37,\n",
    "        38,\n",
    "        39,\n",
    "        40,\n",
    "        41,\n",
    "        42,\n",
    "        43,\n",
    "        44,\n",
    "        45,\n",
    "        46,\n",
    "        47,\n",
    "        48,\n",
    "    ],\n",
    "    \"tensordot\": [\n",
    "        12,\n",
    "        16,\n",
    "        20,\n",
    "        24,\n",
    "        28,\n",
    "        32,\n",
    "        36,\n",
    "        40,\n",
    "        44,\n",
    "        48,\n",
    "        52,\n",
    "        56,\n",
    "        60,\n",
    "        64,\n",
    "        68,\n",
    "        72,\n",
    "        76,\n",
    "        80,\n",
    "        84,\n",
    "        88,\n",
    "        92,\n",
    "        96,\n",
    "        100,\n",
    "        104,\n",
    "        108,\n",
    "        112,\n",
    "        116,\n",
    "        120,\n",
    "        124,\n",
    "        128,\n",
    "        132,\n",
    "        136,\n",
    "        140,\n",
    "        144,\n",
    "        148,\n",
    "        152,\n",
    "        156,\n",
    "        160,\n",
    "        164,\n",
    "        168,\n",
    "        172,\n",
    "        176,\n",
    "        180,\n",
    "        184,\n",
    "        188,\n",
    "        192,\n",
    "        196,\n",
    "        200,\n",
    "    ],\n",
    "    \"tensor\": [\n",
    "        22,\n",
    "        31,\n",
    "        40,\n",
    "        49,\n",
    "        58,\n",
    "        67,\n",
    "        76,\n",
    "        85,\n",
    "        94,\n",
    "        103,\n",
    "        112,\n",
    "        121,\n",
    "        130,\n",
    "        139,\n",
    "        148,\n",
    "        157,\n",
    "        166,\n",
    "        175,\n",
    "        184,\n",
    "        193,\n",
    "        202,\n",
    "        211,\n",
    "        220,\n",
    "        229,\n",
    "        238,\n",
    "        247,\n",
    "        256,\n",
    "        265,\n",
    "        274,\n",
    "        283,\n",
    "        292,\n",
    "        301,\n",
    "        310,\n",
    "        319,\n",
    "        328,\n",
    "        337,\n",
    "        346,\n",
    "        355,\n",
    "        364,\n",
    "        373,\n",
    "        382,\n",
    "        391,\n",
    "        400,\n",
    "        409,\n",
    "        418,\n",
    "        427,\n",
    "        436,\n",
    "        445,\n",
    "    ],\n",
    "}\n",
    "times1 = [\n",
    "    0.01864790916442871,\n",
    "    0.015166997909545898,\n",
    "    0.017799854278564453,\n",
    "    0.021364927291870117,\n",
    "    0.0234529972076416,\n",
    "    0.03243708610534668,\n",
    "    0.03485298156738281,\n",
    "    0.03809309005737305,\n",
    "    0.04254293441772461,\n",
    "    0.043493032455444336,\n",
    "    0.04782605171203613,\n",
    "    0.051072120666503906,\n",
    "    0.05495715141296387,\n",
    "    0.06077980995178223,\n",
    "    0.06451010704040527,\n",
    "    0.06647181510925293,\n",
    "    0.07750391960144043,\n",
    "    0.10012388229370117,\n",
    "    0.09436392784118652,\n",
    "    0.08780503273010254,\n",
    "    0.09475111961364746,\n",
    "    0.08931398391723633,\n",
    "    0.1099538803100586,\n",
    "    0.10660696029663086,\n",
    "    0.10943722724914551,\n",
    "    0.11156201362609863,\n",
    "    0.11216998100280762,\n",
    "    0.11894893646240234,\n",
    "    0.12170791625976562,\n",
    "    0.1290268898010254,\n",
    "    0.13869500160217285,\n",
    "    0.1344318389892578,\n",
    "    0.13837814331054688,\n",
    "    0.14883112907409668,\n",
    "    0.14552593231201172,\n",
    "    0.1480569839477539,\n",
    "    0.14761590957641602,\n",
    "    0.15995121002197266,\n",
    "    0.16048288345336914,\n",
    "    0.16365408897399902,\n",
    "    0.16843199729919434,\n",
    "    0.2130718231201172,\n",
    "    0.17986297607421875,\n",
    "    0.1792001724243164,\n",
    "    0.1941969394683838,\n",
    "    0.2153019905090332,\n",
    "    0.20756793022155762,\n",
    "    0.19938111305236816,\n",
    "]\n",
    "times2 = [\n",
    "    0.010827064514160156,\n",
    "    0.014249086380004883,\n",
    "    0.016450166702270508,\n",
    "    0.020006895065307617,\n",
    "    0.025799989700317383,\n",
    "    0.02879500389099121,\n",
    "    0.03235912322998047,\n",
    "    0.036743879318237305,\n",
    "    0.04072308540344238,\n",
    "    0.04432511329650879,\n",
    "    0.04558587074279785,\n",
    "    0.051867008209228516,\n",
    "    0.05726289749145508,\n",
    "    0.058149099349975586,\n",
    "    0.06532096862792969,\n",
    "    0.0634920597076416,\n",
    "    0.07218098640441895,\n",
    "    0.12434697151184082,\n",
    "    0.07972311973571777,\n",
    "    0.08487296104431152,\n",
    "    0.08191704750061035,\n",
    "    0.13434886932373047,\n",
    "    0.10629105567932129,\n",
    "    0.10842609405517578,\n",
    "    0.10170793533325195,\n",
    "    0.10760092735290527,\n",
    "    0.11115694046020508,\n",
    "    0.1158750057220459,\n",
    "    0.12462496757507324,\n",
    "    0.1272139549255371,\n",
    "    0.13429498672485352,\n",
    "    0.1305849552154541,\n",
    "    0.14617490768432617,\n",
    "    0.18872499465942383,\n",
    "    0.1460709571838379,\n",
    "    0.13549304008483887,\n",
    "    0.1373729705810547,\n",
    "    0.15271997451782227,\n",
    "    0.15703701972961426,\n",
    "    0.1608130931854248,\n",
    "    0.21175909042358398,\n",
    "    0.18168210983276367,\n",
    "    0.17579412460327148,\n",
    "    0.17799592018127441,\n",
    "    0.1961660385131836,\n",
    "    0.20264911651611328,\n",
    "    0.25041794776916504,\n",
    "    0.1808319091796875,\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(\"HMM\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sizes = [\n",
    "    3,\n",
    "    4,\n",
    "    5,\n",
    "    6,\n",
    "    7,\n",
    "    8,\n",
    "    9,\n",
    "    10,\n",
    "    11,\n",
    "    12,\n",
    "    13,\n",
    "    14,\n",
    "    15,\n",
    "    16,\n",
    "    17,\n",
    "    18,\n",
    "    19,\n",
    "    20,\n",
    "    21,\n",
    "    22,\n",
    "    23,\n",
    "    24,\n",
    "    25,\n",
    "    26,\n",
    "    27,\n",
    "    28,\n",
    "    29,\n",
    "    30,\n",
    "    31,\n",
    "    32,\n",
    "    33,\n",
    "    34,\n",
    "    35,\n",
    "    36,\n",
    "    37,\n",
    "    38,\n",
    "    39,\n",
    "    40,\n",
    "    41,\n",
    "    42,\n",
    "    43,\n",
    "    44,\n",
    "    45,\n",
    "    46,\n",
    "    47,\n",
    "    48,\n",
    "    49,\n",
    "    50,\n",
    "]\n",
    "costs = {\n",
    "    \"einsum\": [\n",
    "        7,\n",
    "        9,\n",
    "        13,\n",
    "        15,\n",
    "        19,\n",
    "        21,\n",
    "        25,\n",
    "        27,\n",
    "        31,\n",
    "        33,\n",
    "        37,\n",
    "        39,\n",
    "        43,\n",
    "        45,\n",
    "        49,\n",
    "        51,\n",
    "        55,\n",
    "        57,\n",
    "        61,\n",
    "        63,\n",
    "        67,\n",
    "        69,\n",
    "        73,\n",
    "        75,\n",
    "        79,\n",
    "        81,\n",
    "        85,\n",
    "        87,\n",
    "        91,\n",
    "        93,\n",
    "        97,\n",
    "        99,\n",
    "        103,\n",
    "        105,\n",
    "        109,\n",
    "        111,\n",
    "        115,\n",
    "        117,\n",
    "        121,\n",
    "        123,\n",
    "        127,\n",
    "        129,\n",
    "        133,\n",
    "        135,\n",
    "        139,\n",
    "        141,\n",
    "        145,\n",
    "        147,\n",
    "    ],\n",
    "    \"tensordot\": [\n",
    "        18,\n",
    "        25,\n",
    "        30,\n",
    "        37,\n",
    "        42,\n",
    "        49,\n",
    "        54,\n",
    "        61,\n",
    "        66,\n",
    "        73,\n",
    "        78,\n",
    "        85,\n",
    "        90,\n",
    "        97,\n",
    "        102,\n",
    "        109,\n",
    "        114,\n",
    "        121,\n",
    "        126,\n",
    "        133,\n",
    "        138,\n",
    "        145,\n",
    "        150,\n",
    "        157,\n",
    "        162,\n",
    "        169,\n",
    "        174,\n",
    "        181,\n",
    "        186,\n",
    "        193,\n",
    "        198,\n",
    "        205,\n",
    "        210,\n",
    "        217,\n",
    "        222,\n",
    "        229,\n",
    "        234,\n",
    "        241,\n",
    "        246,\n",
    "        253,\n",
    "        258,\n",
    "        265,\n",
    "        270,\n",
    "        277,\n",
    "        282,\n",
    "        289,\n",
    "        294,\n",
    "        301,\n",
    "    ],\n",
    "    \"tensor\": [\n",
    "        46,\n",
    "        63,\n",
    "        80,\n",
    "        97,\n",
    "        114,\n",
    "        131,\n",
    "        148,\n",
    "        165,\n",
    "        182,\n",
    "        199,\n",
    "        216,\n",
    "        233,\n",
    "        250,\n",
    "        267,\n",
    "        284,\n",
    "        301,\n",
    "        318,\n",
    "        335,\n",
    "        352,\n",
    "        369,\n",
    "        386,\n",
    "        403,\n",
    "        420,\n",
    "        437,\n",
    "        454,\n",
    "        471,\n",
    "        488,\n",
    "        505,\n",
    "        522,\n",
    "        539,\n",
    "        556,\n",
    "        573,\n",
    "        590,\n",
    "        607,\n",
    "        624,\n",
    "        641,\n",
    "        658,\n",
    "        675,\n",
    "        692,\n",
    "        709,\n",
    "        726,\n",
    "        743,\n",
    "        760,\n",
    "        777,\n",
    "        794,\n",
    "        811,\n",
    "        828,\n",
    "        845,\n",
    "    ],\n",
    "}\n",
    "times1 = [\n",
    "    0.02198004722595215,\n",
    "    0.03037405014038086,\n",
    "    0.03350090980529785,\n",
    "    0.04224896430969238,\n",
    "    0.04834318161010742,\n",
    "    0.05909299850463867,\n",
    "    0.06626009941101074,\n",
    "    0.08351302146911621,\n",
    "    0.09097099304199219,\n",
    "    0.08897876739501953,\n",
    "    0.09535503387451172,\n",
    "    0.10136294364929199,\n",
    "    0.13000011444091797,\n",
    "    0.12712597846984863,\n",
    "    0.13105392456054688,\n",
    "    0.1476750373840332,\n",
    "    0.14663481712341309,\n",
    "    0.15439701080322266,\n",
    "    0.15521693229675293,\n",
    "    0.1650080680847168,\n",
    "    0.1742238998413086,\n",
    "    0.17893004417419434,\n",
    "    0.18517208099365234,\n",
    "    0.19159197807312012,\n",
    "    0.20879316329956055,\n",
    "    0.2737429141998291,\n",
    "    0.23352789878845215,\n",
    "    0.22190213203430176,\n",
    "    0.23365497589111328,\n",
    "    0.23900103569030762,\n",
    "    0.2523791790008545,\n",
    "    0.26091718673706055,\n",
    "    0.2820899486541748,\n",
    "    0.3140451908111572,\n",
    "    0.28127598762512207,\n",
    "    0.2906830310821533,\n",
    "    0.34561610221862793,\n",
    "    0.4711790084838867,\n",
    "    0.3032550811767578,\n",
    "    0.31789112091064453,\n",
    "    0.34140491485595703,\n",
    "    0.34586501121520996,\n",
    "    0.3419170379638672,\n",
    "    0.35588693618774414,\n",
    "    0.36873412132263184,\n",
    "    0.36976003646850586,\n",
    "    0.3961608409881592,\n",
    "    0.3883850574493408,\n",
    "]\n",
    "times2 = [\n",
    "    0.022389888763427734,\n",
    "    0.026437997817993164,\n",
    "    0.03232693672180176,\n",
    "    0.041667938232421875,\n",
    "    0.05160379409790039,\n",
    "    0.055931806564331055,\n",
    "    0.07128310203552246,\n",
    "    0.08053183555603027,\n",
    "    0.08122706413269043,\n",
    "    0.0810542106628418,\n",
    "    0.0922250747680664,\n",
    "    0.10212492942810059,\n",
    "    0.11983704566955566,\n",
    "    0.1128089427947998,\n",
    "    0.13935494422912598,\n",
    "    0.12748098373413086,\n",
    "    0.13879609107971191,\n",
    "    0.1859588623046875,\n",
    "    0.14890193939208984,\n",
    "    0.15740394592285156,\n",
    "    0.16302895545959473,\n",
    "    0.17653393745422363,\n",
    "    0.1802539825439453,\n",
    "    0.18121719360351562,\n",
    "    0.20098400115966797,\n",
    "    0.19684600830078125,\n",
    "    0.2023460865020752,\n",
    "    0.22677183151245117,\n",
    "    0.23773717880249023,\n",
    "    0.23118090629577637,\n",
    "    0.23914885520935059,\n",
    "    0.2430558204650879,\n",
    "    0.31301093101501465,\n",
    "    0.2789499759674072,\n",
    "    0.26804518699645996,\n",
    "    0.28461790084838867,\n",
    "    0.3887619972229004,\n",
    "    0.31357502937316895,\n",
    "    0.2947719097137451,\n",
    "    0.3141598701477051,\n",
    "    0.4249720573425293,\n",
    "    0.32235097885131836,\n",
    "    0.3292689323425293,\n",
    "    0.32982301712036133,\n",
    "    0.39942502975463867,\n",
    "    0.3410038948059082,\n",
    "    0.3757472038269043,\n",
    "    0.38117194175720215,\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(\"DBN\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:root] *",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
